
word1 = "intention"
word2 = "execution"

def minDistance(word1,word2):
    m = len(word1)+1    #高度, 因为矩阵需要从[0][0]开始,所以+1
    n = len(word2)+1    #宽度

    dp = [0 for _ in range(n)]
    for j in range(n):
        dp[j] = j

    for i in range(1,m):
        for j in range(1,n):
            if word1[i-1] == word2[j-1]:
                dp[j] = dp[j-1]
            else:
                dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
    return dp[m-1][n-1]

print(minDistance(word1,word2))

